import java.util.ArrayList;
import java.util.HashMap;
import java.lang.Math;


import static java.lang.System.out;

public final class ABMiniMaxDrawFix extends FixedDepth {

    final static Integer ZERO = Integer.valueOf(0);
    final static Integer ONE = Integer.valueOf(1);


    private HashMap<Board, Integer> boardHistory;
    private Board[] drawBoards = new Board[300];
    private int drawBoardsSize = 0;


    public ABMiniMaxDrawFix(boolean isBlack, Eval evaluator, int searchDepth) {
        super(isBlack, evaluator, searchDepth);
	boardHistory = new HashMap<Board, Integer>();
    }




    @Override
    public Board findMove(Board board) {
        // IMPORTANT! If the player using findMove is White, then
        // the search method will be called with BLACK to move and
        // vice versa, i.e. THE RETURN VALUE FROM THE SEARCH-CALL WILL
        // REFLECT THE OPPONENTS BEST POSSIBLE SCORE
        assert board.blackToMove == isBlack;

        int bestValue = MIN;
        if (isBlack) {
            bestValue = MAX;
        }
	int alpha = MIN;
	int beta = MAX;


        ArrayList<Board> moves = board.generateMoves();

	// If no moves found, return null as error flag
	if( moves.isEmpty() ) {
	    return null;
	}
	
	// If only one possible move found - just return that.
	if( moves.size() == 1 ) {
	    return moves.get(0);
	}


        Board bestMove = moves.get(0);
        for (Board move : moves) {
            int value = search(move, searchDepth, alpha, beta);
            if (isBlack) {
                if (value < bestValue) {
		    if (value < beta) {
			beta = value;
		    }
                    bestValue = value;
                    bestMove = move;
                }
            } else {
                if (value > bestValue) {
		    if (value > alpha) {
			alpha = value;
		    }
                    bestValue = value;
                    bestMove = move;
                }
            }
	    //out.println("Considered value " + bestValue);
        }

        if (bestMove != null) {

	    if(printBestMoveValue) {
		out.println("The best move has value " + bestValue);
	    }

	    int nBlack = BitUtils.countBits( bestMove.black );
	    int nWhite = BitUtils.countBits( bestMove.white );

	    // This board can only occur again if there are at least 1 king of each color
	    // and is probably never repeated if > 5 pieces of each
	    if( (board.black & board.kings)!=0 && (board.white & board.kings)!=0 
		&& (nBlack < 6)  && (nWhite < 6) ) { 

		int nOldPieces = BitUtils.countBits( board.black | board.white );
		int nOldKings  = BitUtils.countBits( board.kings );
		int nNewPieces = BitUtils.countBits( bestMove.black | bestMove.white );
		int nNewKings  = BitUtils.countBits( bestMove.kings );

		boolean piecesTaken = (nOldPieces - nNewPieces != 0);
		boolean wasCrowned  = (nOldKings - nNewKings != 0);


		// If this move means no prev. board will come up again
		// - clear the board history (no risk for draws among prev. boards)
		if(piecesTaken || wasCrowned) {
		    boardHistory.clear();
		    drawBoardsSize = 0;
		    //out.println("cleared");
		}
		// Add/increment count of the current move to the board history
		Integer occurrences = boardHistory.get(bestMove);
		if( occurrences != null ) {
		    int o = occurrences + 1;
		    //out.println("Put board in boardHistory with a count of " + o);
		    //GameEngine.printBoard(bestMove);
		    boardHistory.put(new Board(bestMove), o);
		    if(o == 2) {
			drawBoards[drawBoardsSize] = new Board(bestMove);
			drawBoardsSize++;
		    }
		}
		else {
		    //out.println("Put a new board in boardHistory with a count of 1");
		    boardHistory.put(new Board(bestMove), ONE);
		}
	}


        }

        return bestMove;
    }

    public int search(Board board, int depthLeft, int alpha, int beta) {

        ArrayList<Board> moves = board.generateMoves();
        //If unable to move, this is a losing board for current color
	//PUNISH for depth left (embarrassing to lose with much depth left), 
	//i.e. exaggerate the loss. 
	if(moves.isEmpty()) {
            if (board.blackToMove) {
                return BLACK_LOSS+depthLeft;
            } else {
                return WHITE_LOSS-depthLeft;
            }
        }

	for(int i = 0; i < drawBoardsSize; i++) {
	    if ( board.isSame(drawBoards[i]) && isBlack) {
		return DRAW;
	    } else if ( board.isSame(drawBoards[i]) && !isBlack ) { 
		return -DRAW;
	    }
	}


        if(depthLeft == 0) {
            return evaluator.eval(board);
        }

        depthLeft--;
	int nodeCount = 0;
        while (  (nodeCount < moves.size())  &&  (alpha < beta)  ) {
	    Board move = moves.get(nodeCount);
	    int value = search(move, depthLeft, alpha, beta);
            if (board.blackToMove) {
                if (value < beta) {
                    beta = value;
                }   
            } else {
                if (value > alpha) {
                    alpha = value;
                }
            }
	    nodeCount++;
        }

	int bestValue;
        if (board.blackToMove) {
            bestValue = beta;
        } else {
            bestValue = alpha;
        }

        return bestValue;
    }
}
